
import java.awt.Point;

public class GlobalAligner implements SequenceAligner {
	String str1;
	String str2;
	int[][] matrix;
	Point[][] path;

	GapPenalty penaltyFunction;
	AlignmentScore scoreFunction;

	String algn1 = "";
	String algn2 = "";

	public void setSequences(String str1, String str2) {
		this.str1 = str1;
		this.str2 = str2;
	}

	public void setAlignmentScoreFunction(AlignmentScore function) {
		scoreFunction = function;
	}

	public void setGapPenaltyFunction(GapPenalty function) {
		penaltyFunction = function;
	}

	public boolean init() {
		matrix = new int[str1.length() + 1][str2.length() + 1];
		path = new Point[str1.length() + 1][str2.length() + 1];
		for (int i = 0; i < matrix.length; i++) {
			matrix[i][0] = penaltyFunction.gapPenalty(i, 0);
		}
		for (int i = 1; i < matrix[0].length; i++) {
			matrix[0][i] = penaltyFunction.gapPenalty(0, i);
		}
		return true;
	}

	public void align() {
		for (int i = 1; i < matrix.length; i++) {
			for (int j = 1; j < matrix[i].length; j++) {
				getLocalPath(i, j);
			}
		}
	}

	public void traceBack() {
		Point curr = getTrackBackStartPoint();
		if (curr == null) {
			return;
		}

		Point prev = null;
		for (Point next = getNextPath(curr); !isTraceBackEnd(curr); next = getNextPath(curr)) {
			appendAlignment(prev, curr, next);
			prev = curr;
			curr = next;
		}
	}

	protected Point getNextPath(Point current) {
		if (current == null) {
			return null;
		}
		return path[current.x][current.y];
	}

	protected boolean isTraceBackEnd(Point current) {
		return getNextPath(current) == null;
	}

	protected void appendAlignment(Point prev, Point current, Point next) {
		if (current == null) {
			return;
		}

		if (next == null) {
			algn1 = str1.charAt(current.x - 1) + algn1;
			algn2 = str2.charAt(current.y - 1) + algn2;
		}

		if (current.x == 0 && current.y == 0) {
			return;
		}

		if (next.x == current.x) {
			algn1 = "-" + algn1;
		} else {
			algn1 = str1.charAt(current.x - 1) + algn1;
		}

		if (next.y == current.y) {
			algn2 = "-" + algn2;
		} else {
			algn2 = str2.charAt(current.y - 1) + algn2;
		}
	}

	protected Point getTrackBackStartPoint() {
		return new Point(str1.length(), str2.length());
	}

	protected void getLocalPath(int x, int y) {
		int top = matrix[x][y - 1] + penaltyFunction.gapPenalty(x, y);
		int left = matrix[x - 1][y] + penaltyFunction.gapPenalty(x, y);
		int align = matrix[x - 1][y - 1] + scoreFunction.score(matrix, x, y);
		int max = Math.max(Math.max(top, left), align);
		matrix[x][y] = max;

		// higher
		if (max == top) {
			path[x][y] = new Point(x, y - 1);
		} else if (max == align) {
			path[x][y] = new Point(x - 1, y - 1);
		} else {
			path[x][y] = new Point(x - 1, y);
		}

		// lower
		/*
		 * if (max==left) { path[x][y]= new Point(x-1,y); } else if (max==align) {
		 * path[x][y] = new Point(x-1,y-1); } else { path[x][y] = new Point(x,y-1); }
		 */
	}

	public String getAlignedStr1() {
		return algn1;
	}

	public String getAlignedStr2() {
		return algn2;
	}

}
